package 二叉树层序遍历.二叉树层序遍历I;

import java.util.*;

public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        // 使用队列进行树的层序遍历
        // 思路：借用一个last指针,该指针指向每一层的最后一个节点
        // 遍历树的过程中，不断的从队列中pop出一个节点并将该节点的左右孩子入队，当pop的元素和last指针相同的时候，就需要跟新last指针为当前队列的最后一个元素

        if (root == null)
            return Collections.emptyList();
        List<List<Integer>> result = new ArrayList<>();
        // 存放待遍历的树节点
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        // 初始化，启动遍历
        TreeNode last = root;
        queue.offer(root);
        TreeNode p;
        List<Integer> list = new ArrayList<>();
        // 只要队列不为空，就说明还未遍历结束
        while (!queue.isEmpty()) {
            p = queue.poll();
            list.add(p.val);
            // 将该节点的左右孩子都入队
            if (p.left != null) queue.offer(p.left);
            if (p.right != null) queue.offer(p.right);
            // 当 last == p 时，就代表了这一层的树节点已经遍历结束
            if (p == last) {
                // 更新 last 指针
                last = queue.peekLast();
                result.add(list);
                list = new ArrayList<>();
            }
        }
        return result;
    }
}